Portable electronic devices, such as those configured to be handheld or otherwise associated with a user, are employed in a wide variety of applications and environments. Increasingly, such devices are equipped with one or more sensors or other systems for determining the position or motion of the portable device. Notably, devices such as smartphones, tablets, smart watches or other portable devices may feature Global Navigation Satellite Systems (GNSS) receivers, low cost Micro Electro-Mechanical Systems (MEMS) inertial sensors, barometers and magnetometers. GNSS and multi-sensors can be integrated to provide promising positioning results in most outdoor environments. However, some mass market applications require seamless positioning capabilities in all kinds of environments such as malls, offices or underground parking lots. In the absence of GNSS signals in indoor environments, the conventional strapdown Inertial Navigation System (SINS) that uses low cost inertial sensors, suffers significant performance degradation due to the accumulated sensor drifts and bias. As such, positioning technologies relying solely on motion sensors may not satisfy all requirements for seamless indoor and outdoor navigation applications.
Pedestrian Dead Reckoning (PDR) is an example of portable device indoor/outdoor positioning techniques, and has become the focus of industrial and academic research recently. Similar to the SINS, PDR accumulates successive displacement from a known starting point to derive the position. This displacement (step length) can be estimated with various algorithms within a certain accuracy using the inertial sensor measurements. The position error using step lengths from PDR accumulates much slower than that from the accelerometer derived displacement from SINS. The PDR shows improved performance over SINS without GNSS updates. However, PDR still lacks robustness because of the accumulated heading error. This shortcoming may cause a skewed path over time and produce position estimates that might not be consistent with the building layout. Therefore, the resulting navigation trajectories may cross walls, floors or other obstacles. In order to avoid these types of navigation trajectory and building layout inconsistencies, map information may be used to constrain the PDR solution to areas indicated as possible routes or a determined position may be updated to match an assumed position derived from map information. As used herein, the map aided techniques of this disclosure include either or both of constraining the derived position of a user or updating a derived position to a position determined from map information.
As mentioned, map information can be used to improve both the reliability and positioning accuracy of the navigation system. In order to use map information in a navigation system, various map aided algorithms have been proposed and applied in the prior art. Map aided algorithms can be generally classified into four categories: geometric, topological, probabilistic and other advanced techniques.
Geometric map aided algorithms typically consider only the geometric relationship between a user position and a map. They are widely used in the vehicle navigation application in which spatial road networks are abstracted as node points and curves. The most commonly used geometric map-aided algorithm is a point-to-point aided technique that matches the user position to a closest node point of a road segment. While easy to implement, it is sensitive to the way the road network was digitized. Another geometric map-aided algorithm is point-to-curve aided. Such techniques match user positions to the closet curve of a road. Each of the curves comprises line segments which are piecewise linear. Distance may be calculated from the user position to each of the line segments. The line segment that gives the smallest distance is selected as the matched road. Although it is more efficient than point-to-point aided, it may be unstable in dense road networks. Yet another geometric algorithm is curve-to-curve aided, which matches a short history of a user trajectory to curves of roads and may chose a road curve with the shortest distance to the user trajectory. Unfortunately, this approach is quite sensitive to outliers and often gives unexpected results as a result.
Topological map aided algorithms make use of historical user trajectory information, (which might include the previously identified road segment) and topological information such as link connectivity, road classification, road restriction information (single direction, turn restrictions), in addition to the basic geometric information. Various previous works have applied topological information at different levels. For example, (i) using topological information to identify a set of candidate links, (ii) and to identify correct link from a set of candidate links. Therefore, topological map aided algorithms normally outperform algorithms relying only on geometric techniques. Moreover, a weight-based topological map aided may further improve the match aided performance. Such techniques use the correlation values in network geometry and topology information and positioning information from a GPS/DR integrated system as the weight for different road link candidates. The link with the highest weight score may be selected as the correct road segment. However, the misidentification of a road link in previous epoch may have significant negative effects on the following map aided results.
Conventional probabilistic map aided algorithms use an error elliptical or rectangular region around the user position from the navigator. The error region depends on the variance of the estimated navigation position. The error region is then superimposed on the road network to identify a road segment on which the user is travelling. If an error region contains a number of segments, then the evaluation of candidate segments are carried out using heading, connectivity, and closeness criteria. In order to improve the computation efficiency and system reliability, the error region can be only constructed when the user travels through a junction. This is because the construction of an error region at each epoch may lead to incorrect link identification when other road links are close to the link on which the user is travelling.
Advanced map aided algorithms generally refer to more advanced techniques such as Kalman filters, particle filters, fuzzy logic models or Bayesian inferences. For example, a Kalman filter may be used to propagate the user position either from GPS or GPS/DR and to re-estimate the user position to reduce the along track error by using an orthogonal projected map matched position. Similar concepts may also be used with a particle filter to predict and update the user's position. Further, a fuzzy inference system may be used to derive the matched road link with i) the distance between the user position and candidate links and ii) the difference between the platform direction and the link direction. A still further example is the use of a Multiple Hypothesis Technique (MHT) for map aided, by employing pseudo measurements (projected position and heading) from all possible links within the validation region of the current user's position and a topological analysis of the road networks to derive a set of hypotheses and probabilities.
Despite the variety of conventionally available map aided algorithms, either geometric, topological, probabilistic or advanced methods, all may be considered to be based on the assumption that a user is constrained to the network of roads which can be abstracted as linked points, lines and curves. While this assumption may be sufficiently valid in many outdoor land vehicle navigation applications, a problem may be encountered in complex indoor environments, where the rooms, elevators, corridors and similar structures cannot be simplified as the aforementioned points, lines and curves. Some researchers use particle filters with geometric constraint (walls, inaccessible areas) information from a building floor plan to improve the indoor positioning accuracy, however, a user can enter or exit rooms in a random way and simple geometric constraints are undesirable in these scenarios. Furthermore, such techniques have not accommodated multi-floor situations. In contrast, conventional multi-floor map-aided techniques have relied only on geometric information to identify the location of stairs. Such approaches may not be sufficiently reliable, particularly when drift in the navigation solution occurs. Furthermore, most of the existing map aided algorithms ignore the user motion status information. The user's motion status such as going up/down stairs, standing/walking on escalators, or using elevators is beneficial to validate the candidate matched level change links or objects in the indoor navigation applications. Although the advanced algorithms such as fuzzy logics or particle filters have the potential to offer improved performance, they may not be generally suitable for real-time or causal applications due to the heavy computation burden.
Accordingly, it would be desirable to provide navigation techniques using available map information, particularly indoor maps, to enhance the accuracy and reliability of positioning applications for portable devices. It would similarly be desirable to provide map information aided techniques that operate well with seamless outdoor and indoor transition as well as handling multi-level indoor maps to reliably navigate a user in a complex multi-level indoor environment. It would further be desirable to provide map information aided techniques that operate in real time with a portable device employing motion sensors. Moreover, it would be desirable to provide map aided techniques adapted for efficient operation in client and server modes, by enabling a server to use uploaded position and motion information of a user to generate map matched results and the results for real-time navigation. As will be described in the following materials, this disclosure satisfies these and other needs.